package algorithm.sort;

/**
 * 归并排序 - 递归 空间复杂度 提升的高。
 * java 内部和py内部都是用的这种排序。
 *
 *
 */
public class Merge {
    public static void main(String[] args) {
        System.out.println("归并排序");
        // 初始化数组队列
        int [] ay = {-1,2,-99,21,0,11,88,-2,66};

        // 思想如果两个数组已经有序如何排序？
        // [1 4 6 7 10] [2 3 5 8 9] 这俩如何排序？
        // 1、找三个指针
        /**
         * 重新分配一块另外的空间 和原数组等长
         *
         * 第一个指针指向原数组的开始位置 i
         * 第二个指针指向原数组的中间位置就是第二块数组的开始位置 j。
         * 第三指针指向新数组的起始位置 k。
         *
         *
         */
        // 2、第二部开始拿 i 和 j 对比 小的落入 新数组 大的不动 小的指针往后走一下。
        Merge.sort(ay);
        // System.out.println(Merge.f(100 ));
    }
    public static void sort(int [] source){

        split(source, 0, source.length - 1);


        for (int is:source){
            System.out.print(is + " ");
        }


        System.out.println("==============");

        new MyselfMergeSort().sort();
    }
    // 递归拆分数组
    private static void split(int []source, int i, int j){
        if(i < j){
            // 分割
            int m = (j + i) / 2;
            // 左边递归
            split(source, i, m);
            // 右边递归
            split(source, m + 1, j);

            // 遍历完毕后开始进行数组的合并
            merge(source, i, m, j);
        }
    }
    // 合并数组merge
    private static void merge(int []source, int i, int m, int j){
        // 开辟内存空间
        int [] tmp = new int[j - i + 1];
        // 创建游标 存储游标
        int k = 0;
        // 左边
        int left = i;
        // 右边
        int right = m + 1;

        // 两个数组开始对比
        while (left <= m && right <= j){
            if(source[left] > source[right]){
                tmp[k++] = source[right++];
            }else{
                tmp[k++] = source[left++];
            }
        }

        // 归纳合并没有排序的内容
        while (left <= m) tmp[k++] = source[left++];
        while (right <= j) tmp[k++] = source[right++];

        // 写回去
        int ma = 0;
        for(int x = i; x <=j; x++){
            source[x] = tmp[ma++];
        }

    }

    // 递归
    public static int f(int n){
        if(n < 1)
            return 0;
        else
            return n + f(n-1); // 每次都分配一个栈针， 返回值是存在寄存器里面的。 没调用完栈针不消失 所以都挤压在内存里面占用空间。执行完释放。
    }
}


class MyselfMergeSort{
    private int [] list = {-1,2,-99,21,0,11,88,-2,66};

    public void sort(){

        split(list, 0, list.length - 1);

        for(int i:list){
            System.out.print(i + " ");
        }
    }

    private void split(int [] source, int i, int j){

        // 开始树形递归的拆分
        if(i < j){
            // 取出中间值
            int m = (i + j) / 2;
            // 左序遍历
            split(source, i, m);

            // 右序遍历
            split(source, m + 1, j);

            // 排序两个队列
            merge(source, i, m, j);
        }

    }
    // 进行合并写回到source
    private void merge(int [] source, int i, int m, int j){

        // 开辟内存空间
        int []merge = new int[j - i + 1];

        // 申请指针空间
        // 左边数组
        int left = i;
        // 右边起始位置
        int right = m + 1;
        // 空间指针
        int k = 0;

        // 排序
        while (left <= m && right <= j){
            if(source[left] > source[right]){
                merge[k++] = source[right++];
            }else{
                merge[k++] = source[left++];
            }
        }

        // 清空所有的队列
        while (left <= m) merge[k++] = source[left++];
        while (right <= j) merge[k++] = source[right++];

        // 回写
        int ks = 0;
        for(int is = i; is <= j; is++){
            source[is] = merge[ks++];
        }

    }

}